Round Overview
Discuss this match
Division 1 in SRM 515 was a race against the clock, as competitors fixed time by rotating a clock, worked with a shopkeeper who worked around the clock, and then solved the expected walking distance of three friends (who presumably were going to meet for tea at 4 o’clock). Only three competitors beat the clock to solve all three problems, with Petr coming out on top with his 76th room win. Clocking in at 2nd and 3rd, respectively, were two other targets, bmerry and rng_58.
Division 2 saw competitors fortunate enough to work with Fortunate numbers, the trials and tribulations of clock rotation, and some shopkeeping in a significantly less busy shop. Taking home his first win was GHY on the strength of three correct problems and two successful challenges. bapcoi took second place, as the only other person to solve all three problems. Taking third place was onigiri, with two correct problems and four strong challenges.
FortunateNumbers
Problem Details
Used as: Division Two - Level One:
Value | 250 |
Submission Rate | 969 / 1093 (88.66%) |
Success Rate | 878 / 969 (90.61%) |
High Score | ajeet2009057 for 249.96 points (0 mins 21 secs) |
Average Score | 203.45 (for 878 correct submissions) |
In solving this problem, there are two key subproblems to consider:
1) Is a number fortunate? To test this, we look at each digit in decimal notation, and reject the number if it is not 5 or 8. A function that checks if a number is fortunate may look like this:
1
2
3
4
5
6
7
8
9
boolean isFortunate(int n) {
do {
int onesDigit = n % 10;
if (onesDigit != 5 && onesDigit != 8)
return false;
n /= 10;
} while (n > 0);
return true;
}
2) Have we already seen this number? As each number in a, b and c are in [1,30000], you can simply create an array of size 100000, and set the value of that position in the array to true when you encounter a number. A Java solution for this, using the function developed in part 1, is as follows:
1
2
3
4
5
6
7
8
9
10
11
12
public int getFortunate(int[] a, int[] b, int[] c) {
boolean numberFound[] = new boolean[100000];
for (int i = 0; i < a.length; i++)
for (int j = 0; j < b.length; j++)
for (int k = 0; k < c.length; k++)
numberFound[a[i] + b[j] + c[k]] = true;
int ret = 0;
for (int i = 1; i < 100000; i++)
if (numberFound[i] && isFortunate(i))
ret++;
return ret;
}
Used as: Division Two - Level Two:
Value | 500 |
Submission Rate | 495 / 1093 (45.29%) |
Success Rate | 319 / 495 (64.44%) |
High Score | ajeet2009057 for 499.69 points (0 mins 43 secs) |
Average Score | 267.24 (for 319 correct submissions) |
Used as: Division One - Level One:
Value | 250 |
Submission Rate | 690 / 740 (93.24%) |
Success Rate | 617 / 690 (89.42%) |
High Score | Fanazhe for 249.16 points (1 mins 39 secs) |
Average Score | 171.48 (for 617 correct submissions) |
Let’s begin by looking at the description of the clock itself. A key point is that there are only twelve marks on the clock, and that the hands point to one of those marks at 00:00. This means that we can brute force over all possible clock orientations, as long as we can find an efficient way to check if there is a solution at a given orientation.
Let us assume that we have locked the clock at one specific orientation. The constraints of the problem force the hour and minute hands to have an angle that is an integral number of degrees. The hour hand takes 12 hours (or 720 minutes) to complete one revolution of 360 degrees; this means that the hour hand moves exactly 1 degree every two minutes. The minute hand takes 60 minutes to complete one revolution; thus, during those same two minutes that it takes the hour hand to move 1 degree, the minute hand moves 12 degrees. We now have the basis for a very simple brute force algorithm: for each orientation, step through every two minutes from 00:00 to 11:58, and see if the hour and minute hands match the given information. If so, we return that value; otherwise return an empty String. There are only 360*12 = 4320 states, which can easily be brute forced in time.
To be more efficient, we can note that, given the position of the hour hand, we can calculate the exact position of the minute hand in constant time; the minute hand should be located at (hourHand*12)%360. This solution will check exactly 12 states before determining that there is no solution.
In the above analysis, I did not consider the case if multiple times yielded the same values for hourHand and minuteHand. Let us assume that this happens at 00:00, and at the next time t minutes later; we know that this must be between 01:00 and 02:00. Since the minute hand moves 12 times faster than the hour hand, we can show:
12t - 360 = t
11t = 360
t = 360/11
In fact, it turns out that the next time point at which the hands are pointing in the same direction with integral degree values is when the hands are pointing at 00:00 again. Thus, the answer we achieve is unique, and we can just return the first answer we encounter.
1
2
3
4
5
6
7
8
9
10
11
12
13
public String getEarliest(int hourHand, int minuteHand) {
for (int mark = 0; mark < 360; mark += 30) {
int hour = (hourHand + mark) % 360;
int minute = (hour * 12) % 360; // minute hand moves 12 times faster
if (minute == (minuteHand + mark) % 360) {
hour = hour / 30;
minute = minute / 6;
return String.format("%02d:%02d", hour, minute);
}
}
return "";
}
Used as: Division Two - Level Three:
Value | 1000 |
Submission Rate | 11 / 1093 (1.01%) |
Success Rate | 2 / 11 (18.18%) |
High Score | GHY for 523.79 points (34 mins 36 secs) |
Average Score | 468.85 (for 2 correct submissions) |
To analyze this problem, we should break it down into three parts:
1) For the simpler problem of exactly 1 customer, what is the expected profit? Since the customer comes to the store at most once, as soon as he walks in the door, we should sell him the sword. Here, the expected profit is the sum of PtCt, for all possible times t at which a customer could come.
2) In the case of exactly 1 customer, what is the expected profit if we know that he has not come before time t? Now, we begin to discuss conditional probability (for those unfamiliar with this subject, you may find supernova’s tutorial very useful). Let’s assume that there are three possible times that the customer can come, and the probabilities of coming those times are {.2, .4, .2}. 20% of the time, the customer will show up at the first time slot. The remaining 80% of the time, he will not come. When we get to the second time slot, the probability that he will come then is now .4 / (1-.2) = 50%. Similarly, the probability that he will come in the third time slot, knowing that he didn’t come during the first slot, is .2/(1-.2) = 25% . If the customer doesn’t come again during the second time slot, we can update the probability of the third in the same way. Therefore, if we know that the customer arrives after time t, we can recalculate the conditional probabilities, and use those probabilities in step 1 to determine the expected profit.
3) How do we solve the case with two customers? Assume the customers are numbered 1 and 2. Without loss of generality, assume that Customer 1 is the first customer to arrive at the store at time t. At this point, we have two options: sell the sword to him and profit Ct, or wait for Customer 2 and gain an expected profit as solved in part 2 above. We take whichever option yields the higher expected profit. If there was a time t in which a customer could enter and doesn’t, we divide all of that customer’s probabilities by (1-Pt), and multiply the expected profit by that number as well.
Thus, our solution is at worst O(H2), where H is the number of hours in the day; this will easily run within the time limit.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int T[][], C[][];
double P[][];
// getExpected returns the expected profit, assuming the customer
// has skipped the first index chances he had to walk in
double getExpected(int customer, int index) {
double p = 1.0;
for (int i = 0; i < index; i++)
p -= P[customer][i];
double ret = 0;
for (int i = index; P[customer][i] > -1; i++)
ret += P[customer][i] / p * C[customer][i];
return ret;
}
public double getMaximum(String[] customers) {
T = new int[2][20];
C = new int[2][20];
P = new double[2][20];
// Read in the values of the customers to T/C/P
for (int i = 0; i < customers.length; i++) {
Arrays.fill(P[i], -1);
String[] temp = customers[i].split(" ");
for (int j = 0; j < temp.length; j++) {
String[] t = temp[j].split(",");
T[i][j] = Integer.valueOf(t[0]);
C[i][j] = Integer.valueOf(t[1]);
P[i][j] = Integer.valueOf(t[2]) / 100.0;
}
}
double ret = 0.0, p1 = 1, p2 = 1;
int t1 = 0, t2 = 0;
for (int h = 0; h < 24; h++) // For each hour
// If customer 0 walks in at this time, calculate the expected value
if (T[0][t1] == h) {
ret += (P[0][t1] / p1) * p1 * p2 * Math.max(C[0][t1], getExpected(1, t2));
// update these variables, assuming he didn't come in now
p1 -= P[0][t1];
t1++;
}
// If customer 1 walks in at this time, calculate the expected value
else if (T[1][t2] == h) {
ret += (P[1][t2] / p2) * p1 * p2 * Math.max(C[1][t2], getExpected(0, t1));
// update these variables, assuming he didn't come in now
p2 -= P[1][t2];
t2++;
}
return ret;
}
Used as: Division One - Level Two:
Value | 550 |
Submission Rate | 88 / 740 (11.89%) |
Success Rate | 57 / 88 (64.77%) |
High Score | Petr for 443.50 points (14 mins 40 secs) |
Average Score | 258.49 (for 57 correct submissions) |
This problem was a harder version of the division 2 hard problem, in which there are now several swords to sell, and potentially up to 24 customers. The first question that should come up when looking at a problem like this is whether or not there is a way to use dynamic programming to solve this problem. To do so, we need to define a subproblem that can be used as a building block to solve the original problem.
Subproblem: Given a time t, your remaining swords, and a list of which customers have visited the store, calculate the expected profit if you select optimally. We can represent this state as (t, swords, list). At a given time, there is at most one customer who can walk into your store. If that customer has been to your store already, or if there is no customer in that time slot, we can move directly to (t+1, swords, list). Otherwise, that customer will come with probability Pt. If they do not enter then, then your expected profit is (1-Pt)*(t+1, swords, list). If the customer does come in, then you have to decide whether to sell the sword at profit Ct + (t+1, swords-1, list + custt), or not to sell it, with profit (t+1, swords, list + custt); your expected profit from this case is Pt times the maximum of those two profits. Your base cases occur when there are no swords left, or the day is over; in either case, you return 0. This algorithm is O(HS2customers), where H is the number of hours in the day and S is the number of swords. This will certainly time out in the worst case of 24 customers, each entering at their own time (approximately 9 billion states possible).
To improve this algorithm to the point where it can pass, we note that we don’t really need to keep track of all customers who enter the store; the only ones who we need to remember are those customers who may enter the store at multiple times. With the constraints given in this problem, there can be at most 12 repeat customers, which reduces the number of states to just over 2 million. With proper memoization, this solution will easily pass in time.
As was described in the Division 2 Hard section, we do need to update the probabilities before we do any of the processing. For example, a customer has three times where he will come to the store; the probabilities of those three times are {20%, 40%, and 20%}. If the customer does not come during the first hour, then we know that the probability that he will show up in the other hours has increased. Specifically, the probability that he will show up in the second hour (knowing that he did not show up in hour 1) becomes 40% / (100% - 20%) = 50%. Similarly, if he doesn’t show up in hour two, the odds he will show up during hour 3 are 20% / (100%-20%-40%) = 50%. Thus, we need to update the probabilities for all customers with multiple visits, to take into account the knowledge that they didn’t show up during previous hours.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int C[], cID[];
double P[];
boolean visited[][][];
double memo[][][];
double doit(int swords, int hour, int mask) {
if (swords == 0 || hour == 24) // base case
return 0.0;
if (visited[swords][hour][mask]) // memo
return memo[swords][hour][mask];
visited[swords][hour][mask] = true;
if (P[hour] == -1) // if no one comes at this hour
return memo[swords][hour][mask] = doit(swords, hour + 1, mask);
int cMask = cID[hour] < 100 ? (1 << cID[hour]) : 0;
// if this is a multi-visit customer and he's been here, ignore him
if ((cMask & mask) > 0)
return memo[swords][hour][mask] = doit(swords, hour + 1, mask);
// case 1 - the customer doesn't show now
memo[swords][hour][mask] = (1.0 - P[hour]) * doit(swords, hour + 1, mask);
// case 2 - the customer DOES show
memo[swords][hour][mask] += P[hour] * Math.max(doit(swords, hour + 1, mask | cMask),
C[hour] + doit(swords - 1, hour + 1, mask | cMask));
return memo[swords][hour][mask];
}
public double getMaximum(int swords, String[] customers) {
int N = customers.length;
C = new int[24];
cID = new int[24];
P = new double[24];
visited = new boolean[swords + 1][24][5000];
memo = new double[swords + 1][24][5000];
for (int i = 0; i <= swords; i++)
for (int j = 0; j < 24; j++) {
Arrays.fill(visited[i][j], false);
Arrays.fill(memo[i][j], 0);
}
Arrays.fill(P, -1);
int oneVisitIndex = 100, multiVisitIndex = 0;
// Read in the values of the customers to C/P
for (int i = 0; i < customers.length; i++) {
String[] temp = customers[i].split(" ");
double prob = 1.0;
int index = temp.length > 1 ? multiVisitIndex++ : oneVisitIndex++;
for (int j = 0; j < temp.length; j++) {
String[] t = temp[j].split(",");
int hour = Integer.valueOf(t[0]);
C[hour] = Integer.valueOf(t[1]);
double thisProb = Integer.valueOf(t[2]) / 100.0;
P[hour] = thisProb / prob;
prob -= thisProb;
cID[hour] = index;
}
}
return doit(swords, 0, 0);
}
Used as: Division One - Level Three:
Value | 1000 |
Submission Rate | 13 / 740 (1.76%) |
Success Rate | 6 / 13 (46.15%) |
High Score | Petr for 642.57 points (24 mins 14 secs) |
Average Score | 547.82 (for 6 correct submissions) |
Let us start by considering the simplest algorithm: for each possible location of Lecette, Rabbit and Fox, check all possible endpoints. The optimal meeting spot will be the location with the shortest combined distance. To calculate the distances quickly, we can precompute the shortest distance from any point in the maze to any other point in O(H2W2). The overall algorithm to find the meeting place runs in O(LRFHW), where L, R, and F are the number of starting locations for Lecette, Rabbit and Fox, respectively, and H and W are the height and width of the maze. Due to the fact that L <= HW-2, we can rewrite that as O(RFH2W2), which will time out for the maximum test case.
Due to the fact that R and F are small (both are less than 21), we should be able to iterate over all possible starting locations for them, if we can reduce the run time elsewhere. To try to do so, let us fix the starting locations of Rabbit and Fox. As we have precomputed travel distances, we know how long it will take Fox and Rabbit to get to any spot in the maze; for a cell c in the maze, let us call this distance Dc. We want to find a way to get the minimum meeting cost in O(HW). To solve for all of Lycette’s locations at once, let us create a series of nodes S0, S1… SHW. We add edges between all Si and Si+1. We also add edges from SDc-1 to c, as shown below for a simple case.
Figure 1: A simple graph, and the corresponding added nodes. Dc for the F, R and blank node are 2. Dc for the L nodes are 4.
In this new graph G, we start a BFS from node S0. Any time that we take an edge from S into a cell c in the maze, it corresponds to the fact that Fox and Rabbit can reach that cell in exactly depth steps. Once in the maze, any edge we take corresponds to a step that Lecette would take in order to reach that cell from her starting point. Thus, the depth at which we first encounter an L node in G corresponds to the minimum distance that must be travelled by Lecette, Fox, and Rabbit to meet. Once we have traversed the full graph through BFS, we have the minimum distance for every L node, obtained in O(HW). Each time we encounter an L node for the first time, we add the depth to a counter that sums all of the traveled distances. If any L node is not visited in this BFS, then the three cannot meet in this configuration, so we return the empty string. By looping through all starting locations for Fox and Rabbit, this portion of the loop runs in O(RFHW), with preprocessing time of O(H2W2).
After processing all possible starting locations of Rabbit and Fox, our counter contains the sum of the distances that must be traveled in all possible configurations. To get the average that we need to return, we divide by the number of configurations, which is simply LRF. Before returning, we divide both the numerator and denominator by their GCD. Petr’s codefrom the competition is a very clear illustration of this approach.